package com.dynamicprogram;

public class Solution983 {
    public static int mincostTickets(int[] days, int[] costs) {
        int maxDay = days[days.length - 1];
        int minDay = days[0];
        int[] dp = new int[maxDay + 31];
        for (int i = maxDay, d = days.length - 1; i >= minDay; i--) {
            if (i == days[d]) {
                dp[i] = Math.min(costs[0] + dp[i + 1], Math.min(costs[1] + dp[i + 7], costs[2] + dp[i + 30]));
                d--;
            } else dp[i] = dp[i + 1];
        }
        return dp[minDay];
    }
}
